#include <iostream>
#include <cstring>
using namespace std;

const int N = 1010;

int n, V;       //要输入的货物的数量和背包容量
int v[N], w[N]; //对应货物的体积和价值
int f[N][N];    //状态表示数组

int main()
{
    freopen("cin.txt", "r", stdin);
    memset(f, 0, sizeof f); //初始化一下，因为前面那些不用算的，比如f[0][k]之类的，值就是0
    cin >> n >> V;
    for (int i = 1; i <= n; ++i) //这里从1开始是为了对应状态表示数组的含义，毕竟f[0][k]这种是有意义的，下标又不能为负
        cin >> v[i] >> w[i];
    for (int i = 1; i <= n; ++i)                                       //代表前几个货物可以进集合
        for (int j = 1; j <= V; ++j)                                   //代表现阶段集合的容积
            if (j >= v[i])                                             //如果容得下货物i,或者说f[i-1][j-v[i]]+w[i]有意义
                f[i][j] = max(f[i - 1][j - v[i]] + w[i], f[i - 1][j]); //前面代表放，后面代表不放
            else                                                       //不然就没得比
                f[i][j] = f[i - 1][j];                                 //直接等于即可
    cout << f[n][V];
    return 0;
}